Vốn là cựu cầu thủ của tuyển trẻ Séc, Grygera đã khoác áo tuyển Cộng hòa Séc thi đấu tại giải vô địch bóng đá châu Âu 2004, giải vô địch bóng đá thế giới 2006 và giải vô địch bóng đá châu Âu 2008. Tại giải vô địch thế giới 2006, Grygera đã chạy và tạt pha kiến tạo cho Jan Koller ghi bàn mở tỉ số trong trận đầu tiên của Séc với tuyển Mỹ, giúp Séc thắng 3–0.[18]

Tại giải vô địch châu Âu 2008, Grygera đã dính phải một pha va chạm thô bạo bởi tiền đạo Alexander Frei bên phía tuyển Thụy Sĩ trong nửa hiệp đầu tiên của trận mở màn giải, làm cho dây chằng đầu gối của Frei bị rách và buộc anh phải bỏ lỡ hết giải.[19] Anh là nhân tố thường xuyên trong đội hình tuyển Séc trong chiến dịch vòng loại giải vô địch bóng đá thế giới 2010, anh góp mặt trong 6 trên 10 trận đấu nhưng không đủ để giúp tuyển Séc giành vé dự vòng chung kết vô địch thế giới lần thứ hai liên tiếp. Grygera có lần ra sân thứ 65 và cuối cùng trong màu áo tuyển quốc gia vào tháng 10 năm 2009.